package bintree.leetcode;

/**
 * @Author: yuisama
 * @Date: 2021/9/9 12:38
 * @Description:根据二叉树的前序和中序遍历结果构建二叉树
 * https://leetcode-cn.com/problems/construct-binary-tree-from-preorder-and-inorder-traversal/
 */
public class Num105_BuildTreeByPreAndInOrder {
    /**
     * 先序遍历第一个节点一定是树的根节点，后面的节点就是左子树或者右子树的根节点
     * 中序遍历左子树一定在根节点左侧，右子树一定在根节点右侧
     */
    // index表示当前在先序遍历结果中处理到哪一个元素了
    private int index;
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        return buildTreeHelper(preorder,inorder,0,preorder.length);
    }

    /**
     * 该方法的语义为:给定一个二叉树的前序和中序结果集，构建出一颗二叉树
     * @param preorder 前序遍历集
     * @param inorder 中序遍历集
     * @param left 当前preorder[index]节点对应子树的中序遍历结果
     * @param right
     * @return 构建完成的二叉树的根节点
     */
    private TreeNode buildTreeHelper(int[] preorder, int[] inorder, int left, int right) {
        // 空区间，表示子树为空
        if (left >= right)
            return null;
        // 前序遍历以及处理完毕，返回空
        if (index >= preorder.length)
            return null;
        // 取得前序遍历结果，构建以该结果为根节点的树
        TreeNode root = new TreeNode(preorder[index]);
        // 继续处理下个节点
        index++;
        // 找到该节点在中序遍历结果的位置，将前序遍历结果分成左右子树
        int pos = find(inorder,left,right,root.val);
        root.left = buildTreeHelper(preorder,inorder,left,pos);
        root.right = buildTreeHelper(preorder,inorder,pos + 1,right);
        return root;
    }

    // 找到前序结果集中元素对应的中序结果集中的下标位置
    private int find(int[] inorder, int left, int right, int toFind) {
        for (int i = left; i < right; i++) {
            if (inorder[i] == toFind)
                return i;
        }
        return -1;
    }

}
